package cn.big.algs.learn.sort;

/**
 * 快速排序
 *
 * @author LiJianXin
 * @create 2020/4/22 0022
 */
public class QuickSort {
	public static void main(String[] args) {
		int number = 100000;
		long start = System.nanoTime();
		for (int i = 0; i < number; i++) {
			int[] arr = new int[]{72, 6, 57, 88, 60, 42, 83, 73, 48, 85, 72, 6, 57, 88, 60, 42, 83, 73, 48, 85, 72, 6, 57, 88, 60, 42, 83, 73, 48, 85, 72, 6, 57, 88, 60, 42, 83, 73, 48, 85, 72, 6, 57, 88, 60, 42, 83, 73, 48, 85, 72, 6, 57, 88, 60, 42, 83, 73, 48, 85, 72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
//			quickSort1(arr, 0, arr.length - 1);
			quickSort2(arr, 0, arr.length - 1);
			for (int j : arr) {
				System.out.print(j + ",");
			}
			System.out.println();
		}
		System.out.println("平均计时时：" + (System.nanoTime() - start) / number);
	}

	/**
	 * 快速排序 平均计时：111625
	 */
	private static void quickSort1(int[] arr, int left, int right) {
		if (left < right) {
			int t = partition1(arr, left, right);
			//分治法递归处理
			quickSort1(arr, left, t - 1);
			quickSort1(arr, t + 1, right);
		}
	}


	/**
	 * 挖坑法
	 *
	 * @param arr
	 * @param left
	 * @param right
	 * @return
	 */
	private static int partition1(int[] arr, int left, int right) {
		int pivot = arr[left];
		while (left < right) {
			//先找右边，右边的值小于中值，直到右边的值放到左边坑中
			while (left < right) {
				if (arr[right] < pivot) {
					arr[left] = arr[right];
					left++;
					break;
				}
				right--;
			}
			//后找左边，左边的值大于中值，把左边的值放到右边坑中。
			while (left < right) {
				if (arr[left] > pivot) {
					arr[right] = arr[left];
					right--;
					break;
				}
				left++;
			}
		}
		arr[left] = pivot;
		return left;
	}

	/**
	 * 指针交换法 平均计时：131597
	 * @param arr
	 * @param left
	 * @param right
	 */
	private static void quickSort2(int[] arr, int left, int right) {
		if (left < right) {
			int t = partition2(arr, left, right);
			//分治法递归处理
			quickSort2(arr, left, t - 1);
			quickSort2(arr, t + 1, right);
		}
	}

	/**
	 * 指针交换法
	 *
	 * @param arr
	 * @param left
	 * @param right
	 * @return
	 */
	private static int partition2(int[] arr, int left, int right) {
		int pivot = arr[left];
		while (left < right) {
			//先找右边，右边的值小于中值,停止
			while (left < right && arr[right] > pivot) {
				right--;
			}
			//后找左边，左边的值大于中值,停止
			while (left < right && arr[left] < pivot) {
				left++;
			}
			//交换左值和右值
			if (left < right) {
				int temp = arr[left];
				arr[left++] = arr[right];
				arr[right--] = temp;
			}
		}
		arr[left] = pivot;
		return left;
	}
}
